Đền hiện nay được xây dựng từ thế kỷ 19. Lúc đầu được gọi là chùa Ngọc Sơn (chữ Nho: 玉山), sau đổi gọi là đền Ngọc Sơn vì trong đền chỉ thờ thần Văn Xương Đế Quân là ngôi sao chủ việc văn chương khoa cử và thờ Trần Hưng Đạo, vị anh hùng có công phá quân Nguyên thế kỷ 13.

Khởi nguyên, khi vua Lý Thái Tổ dời đô ra Thăng Long đặt tên ngôi đền đã có tại đây là Ngọc Tượng, đến đời nhà Trần đổi tên là Ngọc Sơn. Thời Trần, ngôi đền để thờ những người anh hùng liệt sĩ đã hy sinh trong kháng chiến chống Nguyên-Mông. Về sau lâu ngày đền ấy sụp đổ.

Đến thời Vĩnh Hựu nhà Lê (1735 - 1739), chúa Trịnh Giang đã dựng cung Thụy Khánh và đắp hai quả núi đất ở trên bờ phía Đông đối diện với Ngọc Sơn gọi là núi Đào Tai và Ngọc Bội. Cuối đời nhà Lê, cung Thụy Khánh bị Lê Chiêu Thống phá hủy. Một nhà từ thiện tên là Tín Trai, nhân nền cung cũ đã lập ra một ngôi chùa gọi là chùa Ngọc Sơn. Bài ký "Đền Ngọc Sơn đế quân" được soạn năm 1843 vào lúc nhân dịp sửa đền Quan đế thành chùa Ngọc Sơn có viết: "...Hồ Tả Vọng tên cũ gọi hồ Hoàn Kiếm là một danh thắng đất Kinh kỳ xưa. Phía bắc mặt hồ, một gò đất nổi lên rộng khoảng ba bốn sào, tương truyền là chỗ đài câu cá thời cuối Lê. Trước đây, ông Tín Trai làng Nhị Khê nhân có đền Quan Đế tại đấy bèn mở rộng sửa sang thêm gọi là chùa Ngọc Sơn...".

Ít năm sau chùa lại nhường cho một hội từ thiện đổi làm đền thờ Tam Thánh. Hội này đã bỏ gác chuông, xây lại các gian điện chính, các dãy phòng hai bên, đặt tượng Văn Xương đế quân vào thờ và đổi tên là đền Ngọc Sơn. Theo bài ký "Sửa lại miếu Văn Xương", thì "...Hiện nay đền thờ mới đã hoàn thành, phía trước kề bờ nước, làm đình Trấn Ba, ngụ ý là cột trụ đứng vững giữa làn sóng văn hóa. Bên tả, phía đông cầu Thê Húc, dựng Đài Nghiên. Lại về phía đông trên núi Độc Tôn, xây Tháp Bút, tượng trưng cho nền văn vật..."

Năm Tự Đức thứ mười tám (1865), nhà nho Nguyễn Văn Siêu đứng ra tu sửa lại đền. Đền mới sửa đắp thêm đất và xây kè đá xung quanh, xây đình Trấn Ba, bắc một cầu từ bờ Đông đi vào gọi là cầu Thê Húc.